package main.leetcode.clockin.September;

/**
 * 117. 填充每个节点的下一个右侧节点指针 II
 *
 * <p>给定一个二叉树
 *
 * <p>struct Node { <br>
 * <span>int val; Node *left; <br>
 * Node *right; <br>
 * Node *next; <br>
 * }
 *
 * <p>填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
 *
 * <p>初始状态下，所有 next 指针都被设置为 NULL。
 *
 * <p>进阶：<br>
 * 你只能使用常量级额外空间。 <br>
 * 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
 *
 * <p>提示：<br>
 * 树中的节点数小于 6000 <br>
 * -100 <= node.val <= 100
 */
public class day28 {
    private Node pre, nextStart;

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right = new Node(3);
        root.right.right = new Node(7);
        System.out.println(new day28().connect(root));
    }

    /** 不使用队列 */
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        // 指定start为每一层的开始节点
        Node start = root;
        while (start != null) {
            pre = null;
            nextStart = null;
            // 对每层已通过next指针建立的链表进行遍历，同时为其下一层的节点之间建立next关联
            for (Node node = start; node != null; node = node.next) {
                if (node.left != null) {
                    helper(node.left);
                }
                if (node.right != null) {
                    helper(node.right);
                }
            }
            start = nextStart;
        }
        return root;
    }

    private void helper(Node node) {
        // 前驱节点不为null，连接next
        if (pre != null) {
            pre.next = node;
        }
        // 寻找下一个新的起点
        if (nextStart == null) {
            nextStart = node;
        }
        // 确定前驱节点
        pre = node;
    }

    //    /** 使用队列 */
    //    public Node connect(Node root) {
    //        if (root == null) {
    //            return null;
    //        }
    //        Queue<Node> queue = new LinkedList<>();
    //        queue.offer(root);
    //        while (!queue.isEmpty()) {
    //            int size = queue.size();
    //            Node pre = null;
    //            for (int i = 0; i < size; ++i) {
    //                Node node = queue.poll();
    //                if (node.left != null) {
    //                    queue.offer(node.left);
    //                }
    //                if (node.right != null) {
    //                    queue.offer(node.right);
    //                }
    //                if (i != 0) {
    //                    pre.next = node;
    //                }
    //                pre = node;
    //            }
    //        }
    //        return root;
    //    }

    private static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }
}
